/**
 * 位图的实现
 */

#ifndef _AHAMOLETT_CLANG_DATASTRUCT_BITMAP_H_
#define _AHAMOLETT_CLANG_DATASTRUCT_BITMAP_H_
#ifdef __cplusplus
extern "C" {
#endif

#include <cds/cds_types.h>


/* 位图的结构体 */
struct bitmap {
    size_t  map_size;   /// 位图的大小字节数。
    union {
        unsigned char   *buffer;    /// 指向存放位图内容的指针。
        /// 与buffer相同，不过将位图作为无符号长整型数组操作位图。
        unsigned long   *buffer_long;
    };
};

/**
 * @brief 映射了一个八位整形数第一个被置位的比特位，0映射为8。
 */
extern unsigned char get_byte_first_set_bit[256];

/**
 * @brief 映射了一个八位整形数最后一个被置位的比特位，0映射为8。
 */
extern unsigned char get_byte_last_set_bit[256];

/**************************** 读取和修改位图的操作 ******************************/
/**
 * @brief 获得一个位号块内偏移的 mask 。 
 * 
 * 获得 val 变量的数据类型的位数减一，用于通过与操作获得位号的块内偏移部分。
 */
#define __type_bits_mask(val)   ((sizeof(val) << 3) - 1)

/**
 * @brief 获得操作某个位的 mask
 * 
 * 计算的值用于操作位图缓冲 bm_buffer 中位号为 bit 的位。
 */
#define __bitmap_bit_mask(bm_buffer, bit)   \
    (1UL << ((bit) & __type_bits_mask(*(bm_buffer))))

/**
 * @brief 获得位图缓冲区的某个位所在变量的指针。
 * 
 * 获得位图缓冲区 bm_buffer 作为数组时，位号为 bit 的位所在数组下项的索引值。
 */
#define __bitmap_block_ptr(bm_buffer, bit)  ({  \
    unsigned long __idx = (bit);    \
    __idx &= ~__type_bits_mask(*(bm_buffer));   \
    __idx >>= 3; \
    (typeof(bm_buffer))((unsigned long)(bm_buffer) + __idx);    \
})

/**
 * @brief 检查位图缓冲区对应位是否被置位。
 */
#define __check_bit(bm_buffer, bit) ({  \
    typeof(bm_buffer) __ptr = __bitmap_block_ptr(bm_buffer, bit);   \
    typeof(*(bm_buffer)) __bit_mask = __bitmap_bit_mask(bm_buffer, bit);    \
    __sync_synchronize();   \
    !!((*__ptr) & __bit_mask);  \
})

/**
 * @brief 置位位图缓冲区对应位。
 */
#define __set_bit(bm_buffer, bit)   ({  \
    typeof(bm_buffer) __ptr = __bitmap_block_ptr(bm_buffer, bit);   \
    typeof(*(bm_buffer)) __bit_mask = __bitmap_bit_mask(bm_buffer, bit);    \
    *__ptr |= __bit_mask;   \
    __sync_synchronize();   \
    !!((*__ptr) & __bit_mask);  \
})

/**
 * @brief 清除位图缓冲区对应位。
 */
#define __clear_bit(bm_buffer, bit) ({  \
    typeof(bm_buffer) __ptr = __bitmap_block_ptr(bm_buffer, bit);   \
    typeof(*(bm_buffer)) __bit_mask = __bitmap_bit_mask(bm_buffer, bit);    \
    *__ptr &= ~__bit_mask;  \
    __sync_synchronize();   \
    !!((*__ptr) & __bit_mask);  \
})

/**************************** 获得位图的元数据与状态 ****************************/
/**
 * @brief 检查位图是否已初始化。
 * 
 * 通过检查位图结构体内元素的状态，判断位图是否已经被初始化。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * 
 * @retval true 位图已经被初始化。
 * @retval false 位图没有被初始化
 */
#define bitmap_is_initialized(bm)   \
    ((bm) != NULL && (bm)->buffer != NULL && (bm)->map_size > 0)

/**
 * @brief 返回位图的长度。
 * 
 * 该函数首先检查位图是否被初始化。如果位图已经被初始化返回位图的长度，否则返回0。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * 
 * @return size_t 位图的长度。
 */
static inline size_t bitmap_size(struct bitmap *bm)
{
    if (bitmap_is_initialized(bm)) {
        return bm->map_size;
    } else {
        return 0;
    }
}

/**
 * @brief 返回位图的总位长。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * 
 * @return unsigned long 位图的总位长。
 */
#define bitmap_length(bm)   ((long)(bitmap_size(bm) << 3))


/******************************* 位图的创建操作 ********************************/
/**
 * @brief 对位图进行初始化。
 * 
 * 根据用户传入的信息初始化一个位图结构体，初始化完成后位图中的所有位都会被清空。
 * 
 * @param bm struct bitmap* 进行初始化的位图。
 * @param buffer void* 存放位图的缓存空间。
 * @param size size_t 位图的大小，必须按照 sizeof(long) 对齐。
 * 
 * @return struct bitmap* 初始化成功返回位图结构体指针，否则返回NULL。
 */
extern struct bitmap *bitmap_init(struct bitmap *bm, void *buffer, size_t size);

/**
 * @brief 清除整个位图。
 * 
 * @param bm struct bitmap* 位图结构体。
 */
extern void bitmap_clear_all(struct bitmap *bm);

/**
 * @brief 置位整个位图。
 * 
 * @param bm struct bitmap* 位图结构体。
 */
extern void bitmap_set_all(struct bitmap *bm);

/**
 * @brief 复制位图。
 * 
 * 根据一个现有的位图，创建一个新的位图。
 * 
 * @param new_bm struct bitmap* 存放副本的位图。
 * @param old_bm struct bitmap* 进行复制的位图。
 * @param buffer void* 存放副本位图的缓存空间。
 * 
 * @return struct bitmap* 复制成功返回位图结构体指针，否则返回NULL。
 */
extern struct bitmap*
bitmap_copy(struct bitmap *new_bm, struct bitmap *old_bm, void *buffer);

/********************************* 检查位图的位 *********************************/
/**
 * @brief 检查位图中某一个位是否被置位。
 * 
 * 如果指定的位存在，会返回该位的状态；如果指定的位不存在，无论如何都会返回false。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * @param bit long 位号。
 * 
 * @retval true 位图中指定的位被置位。
 * @retval false 位图中指定的位不存在或未被置位。
 */
extern int bitmap_check_bit(struct bitmap *bm, long bit);

/**
 * @brief 检查位图中一个范围内的位是否都被置位。
 * 
 * 在位图bm中，检查从beg到end（包括end）的所有位，如果都被置位，返回true，否则返回false。
 * 传入的位图结构体没有被初始化，或者beg和end不合法，都会返回false。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * @param beg 范围内第一位的位数。
 * @param end 范围内最后一位的位数。
 * 
 * @retval true 范围内所有位都被置位。
 * @retval false 范围内存在有没被置位的位，或者输入不合法
 */
extern int bitmap_check_all_set(struct bitmap *bm, long beg, long end);

/**
 * @brief 检查位图中一个范围内的位是否存在位被置位。
 * 
 * 在位图bm中，检查从beg到end（包括end）的所有位，如果存在有被置位的位，返回true，否则返回
 * false。传入的位图结构体没有被初始化，或者beg和end不合法，都会返回false。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * @param beg 范围内第一位的位数。
 * @param end 范围内最后一位的位数。
 * 
 * @retval true 范围内存在位都被置位。
 * @retval false 范围内所有位都没被置位，或者输入不合法。
 */
extern int bitmap_check_any_set(struct bitmap *bm, long beg, long end);

/*************************** 查找位图中符合条件的位与块 **************************/
/**
 * @brief 返回位图中从给定位号开始第一个被置位的位号。
 * 
 * 从给定位号开始遍历整个位图结构体，返回第一个被置位的位号。如果传入的位图无效，返回-1；如果
 * 从给定位号开始整个位图都没被置位，或者传入的位号大于等于位图的长度，返回位图长度。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * @param bit 开始搜索的第一个位的位号。
 * 
 * @return long 从给定位号开始第一个被置位的位号。
 */
extern long bitmap_first_set_bit_from(struct bitmap *bm, long bit);

/**
 * @brief 返回位图中从给定位号开始第一个被清除的位号。
 * 
 * 从给定位号开始遍历整个位图结构体，返回第一个被清除的位号。如果传入的位图无效，返回-1；如果
 * 从给定位号开始整个位图都被置位，或者传入的位号大于等于位图的长度，返回位图长度。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * @param bit 开始搜索的第一个位的位号。
 * 
 * @return long 从给定位号开始第一个被清除的位号。
 */
extern long bitmap_first_unset_bit_from(struct bitmap *bm, long bit);

/**
 * @brief 返回位图中第一个被置位的位号。
 * 
 * 遍历整个位图结构体，返回第一个被置位的位号。如果传入的位图无效，返回-1；如果整个位图都没被
 * 置位，返回-1。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * 
 * @return long 第一个被置位的位号。
 */
#define bitmap_first_set_bit(bm)    bitmap_first_set_bit_from(bm, 0)

/**
 * @brief 返回位图中第一个被清除的位号。
 * 
 * 遍历整个位图结构体，返回第一个被清除的位号。如果传入的位图无效，返回-1；如果整个位图都被
 * 置位，返回-1。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * 
 * @return long 第一个被清除的位号。
 */
#define bitmap_first_unset_bit(bm)  bitmap_first_unset_bit_from(bm, 0)

/**
 * @brief 返回位图中以给定位号开始，连续被置位的位。
 * 
 * 如果位图未被初始化，给定位号过界，或者给定位号的位没有被置位，返回-1。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * @param bit long 位块的起点位号。
 * 
 * @return long 位块的位长。
 */
extern long bitmap_sizeof_set_block(struct bitmap *bm, long bit);

/**
 * @brief 返回位图中以给定位号开始，连续被清除的位。
 *
 * 如果位图未被初始化，给定位号过界，或者给定位号的位没有被置位，返回0。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * @param bit long 位块的起点位号。
 * 
 * @return long 位块的位长。
 */
extern long bitmap_sizeof_unset_block(struct bitmap *bm, long bit);

/**
 * @brief 返回位图中第一个全被置位的块的首个位号。
 * 
 * 遍历整个位图结构体，返回第一个全被置位的块的首个位号。如果传入的位图无效，返回-1；如果整个
 * 位图都没被置位，返回-1。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * 
 * @return long 位图中第一个全被置位的块的首个位号。
 */
#define bitmap_first_set_block(bm)  bitmap_first_set_bit(bm)

/**
 * @brief 返回位图中第一个全被清除的块的首个位号。
 * 
 * 遍历整个位图结构体，返回第一个全被清除的块的首个位号。如果传入的位图无效，返回-1；如果整个
 * 位图都没被置位，返回-1。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * 
 * @return long 位图中第一个全被清除的块的首个位号。
 */
#define bitmap_first_unset_block(bm)    bitmap_first_unset_bit(bm)

/**
 * @brief 返回下一个全部被置位的位块的首个位位号。
 *
 * 从给定的位号开始，返回下一个全部被置位的位块的首个位位号（不包括给定位号所在的位块）。
 * 如果没有下一个位块，给定位号越界，或者给定的位图没被初始化，返回-1。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * @param bit bit long 当前位块的起点位号。
 * 
 * @return long 下一个位块的起点位号，没有则返回0。
 */
extern long bitmap_next_set_block(struct bitmap *bm, long bit);

/**
 * @brief 返回下一个全部被清除的位块的首个位位号。
 * 
 * 从给定的位号开始，返回下一个全部被清除的位块的首个位位号（不包括给定位号所在位块）。
 * 如果没有下一个位块，给定位号越界，或者给定的位图没被初始化，返回-1。
 *
 * @param bm struct bitmap* 位图结构体指针。
 * @param bit long 当前位块的起点位号。
 * 
 * @return long 下一个位块的起点位号，没有则返回0。
 */
extern long bitmap_next_unset_block(struct bitmap *bm, long bit);

/********************************* 设置位图的位 *********************************/
/**
 * @brief 置位给定位号的比特，并返回操作后对应比特的置位状态。
 * 
 * 如果给定的位图未被初始化，或者给定位号越界，该函数不会有任何动作。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * @param bit long 位号。
 * 
 * @retval true 操作后该位被置位。
 * @retval false 操作后后该位没被置位，或传入参数无效。
 */
extern int bitmap_set_bit(struct bitmap *bm, long bit);

/**
 * @brief 清除给定位号的比特，并返回操作后对应比特的置位状态。
 * 
 * 如果给定的位图未被初始化，或者给定位号越界，该函数不会有任何动作。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * @param bit unsigned long 位号。
 * 
 * @retval true 操作后该位依旧被置位，或传入参数无效。
 * @retval false 操作后后该位被清除。
 */
extern int bitmap_clear_bit(struct bitmap *bm, long bit);

/**
 * @brief 置位给定范围内的所有比特。
 * 
 * 如果给定的位图未被初始化，或者beg大于等于end，该函数不会有任何动作。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * @param beg 范围内第一位的位数。
 * @param end 范围内最后一位的位数。
 */
extern void bitmap_set_block(struct bitmap *bm, long beg, long end);

/**
 * @brief 清除给定范围内的所有比特。
 * 
 * 如果给定的位图未被初始化，或者beg大于等于end，该函数不会有任何动作。
 * 
 * @param bm struct bitmap* 位图结构体指针。
 * @param beg 范围内第一位的位数。
 * @param end 范围内最后一位的位数。
 */
extern void bitmap_clear_block(struct bitmap *bm, long beg, long end);

#ifdef __cplusplus
}
#endif
#endif  // #ifndef _AHAMOLETT_CLANG_DATASTRUCT_BITMAP_H_
